package com.alg;

import com.algorithm.TreeNode;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * @author: sun.hongliang
 * @create: 2020/01/30 19:03
 */
public class TreeSumTest {
    public static void main(String[] args) {

    }

    public List<String> binaryTreePaths2(TreeNode root) {
        TreeNode p = root;
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        Queue<String> pathQueue = new LinkedBlockingQueue<>();
        queue.offer(p);
        pathQueue.offer(Integer.toString(p.val));
        List<String> result = new LinkedList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                p = queue.poll();
                String path = pathQueue.poll();
                if (p.left == null && p.right == null) {
                    result.add(path);
                    continue;
                }
                if (p.left != null) {
                    queue.offer(p.left);
                    pathQueue.offer(p.val + "->" + p.left.val);
                }
                if (p.right != null) {
                    queue.offer(p.right);
                    pathQueue.offer(p.val + "->" + p.right.val);
                }
            }
        }
        return result;
    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<>();
        dfs(root, "", res);
        return res;
    }

    private void dfs(TreeNode root, String pre, List<String> res) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            res.add(pre + root.val);
        }
        pre = pre + root.val + "->";
        if (root.left != null) {
            dfs(root.left, pre, res);
        }
        if (root.right != null) {
            dfs(root.right, pre, res);
        }
    }

    /**
     * public List<List<Integer>> pathSum(TreeNode root, int sum) {
     * List<List<Integer>> list = new LinkedList<>();
     * dfs(root, new LinkedList<>(), list, sum);
     * return list;
     * }
     * <p>
     * private void dfs(TreeNode root, List<Integer> path, List<List<Integer>> res, int sum) {
     * if (root == null) return;
     * path.add(root.val);
     * sum -= root.val;
     * if (root.left == null && root.right == null && sum == 0) {
     * res.add(new ArrayList<>(path));
     * }
     * if (root.left != null) {
     * dfs(root.left, path, res, sum);
     * }
     * if (root.right != null) {
     * dfs(root, path, res, sum);
     * }
     * path.remove(path.size() - 1);
     * }
     **/

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new LinkedList<>();
        TreeNode p = root;
        int total = 0;
        Stack<TreeNode> nodeStack = new Stack<>();
        while (p != null && !nodeStack.isEmpty()) {
            while (p != null) {
                nodeStack.push(p);
                total += p.val;
                temp.add(p.val);
                if (p.left == null && p.right == null && total == sum) {
                    res.add(new ArrayList<>(temp));
                }
                p = p.left;
            }
            if (!nodeStack.isEmpty()) {
                p = nodeStack.pop();
                total -= p.val;
                p = p.right;
                temp.remove(temp.size() - 1);
            }
        }
        return res;
    }
}
